package DataStructure.SortMethod;

/**
 * @time: 2021/11/17/017 11:59
 * @author: Zhurunhe
 * @Version：1
 * 二分查找算法
 */
public class BinarySearch {
    /**
     * 1. 如果待查序列为空，那么就返回-1，并退出算法；这表示查找不到目标元素。
     * 2. 如果待查序列不为空，则将它的中间元素与要查找的目标元素进行匹配，看它们是否相等。
     * 3. 如果相等，则返回该中间元素的索引，并退出算法；此时就查找成功了。
     * 4. 如果不相等，就再比较这两个元素的大小。
     * 5. 如果该中间元素大于目标元素，那么就将当前序列的前半部分作为新的待查序列；这是因为后半部分的所有元素都大于目标元素，它们全都被排除了。
     * 6. 如果该中间元素小于目标元素，那么就将当前序列的后半部分作为新的待查序列；这是因为前半部分的所有元素都小于目标元素，它们全都被排除了。
     * 7. 在新的待查序列上重新开始第1步的工作。
     */

    public static void main(String[] args) {
        int[] arr={3, 12, 24, 31, 46, 48, 52, 66, 69, 79, 82};
        int last=arr.length-1;
        int target=4;
        int res = binarySearchIndex(arr, target, 0, last);
        System.out.println(res);
        int insres = insertSearch(arr, target, 0, last);
        System.out.println(insres);
    }

    public static int binarySearchIndex(int[] arr, int target, int index, int last){
        System.out.println("----");
        if (arr.length==0||index>last){
            return -1;
        }
        //取中间指标
//        int tempIndex = (last+index) / 2;
        int tempIndex =index+ (last-index) / 2;
        if (arr[tempIndex] == target) {
            return tempIndex;
        } else if (target > arr[tempIndex]) {
//            System.out.println(target+" : "+arr[tempIndex]+","+tempIndex);
            return binarySearchIndex(arr, target, tempIndex+1, last);
        } else if (target < arr[tempIndex]) {
//            System.out.println(target+" : "+arr[tempIndex]+","+tempIndex);
            return binarySearchIndex(arr, target, index, tempIndex-1);
        }else {
            return -2;
        }
    }
    //插值查找算法，在二分查找算法的基础上优化的一种算法
    public static int insertSearch(int[] arr,int target,int index,int last){
        System.out.println("----");
        if (arr.length == 0 || index > last || target < arr[index]||target>arr[last]) {
            return -1;
        }

        int tempIndex=index+(last-index)*(target-arr[index])/(arr[last]-arr[index]);
        if (target>arr[tempIndex]){
            return insertSearch(arr,target,tempIndex+1,last);
        }else if (target<arr[tempIndex]){
            return insertSearch(arr,target,index,tempIndex-1);
        }else {
            return tempIndex;
        }
    }
}
